﻿using System;
using System.Collections.Generic;
using System.Drawing;
using System.Windows.Forms;
using System.Windows.Forms.VisualStyles;

namespace SlidingPuzzle {

    /// <summary>
    /// Main window for sliding puzzle game.
    /// <BR>
    /// Author: David I. Schwartz (dis@mail.rit.edu)
    ///         Feb 2010, isSolved rewritten by Zach Hoefler
    /// <BR>
    /// </summary>
    public partial class SlidingPuzzle : Form {

        #region Fields and Getters

        public const int DEFAULT_SIZE = 3;                // default size of game board (size x size)
        public const int MAXSCRAMBLES = 3000;             // max # of times player can scramble board
        public static Color DEFAULT_COLOR = Color.Plum;   // default color for each tile on board
        private int tiles;                                 // current game board dim (size x size)
        private Color tileColor;                          // current tile color
        private int tileSize;                             // current size of game tile (size x size) (pixels)
        private bool numbersOn;                           // are numbers displayed on tiles?
        private int timeSoFar;                            // how much time has elapsed during current game (sec)
        private int moves;                                // how many moves made in current game
        private Button[,] buttons;                        // collection of board buttons ("tiles")
        private const string BUTTON_NAME = "tile";        // default base tile name
        private Point blankLoc;                           // location of "blank tile"

        /// <summary>
        /// Return current tile color.
        /// </summary>
        public Color CurrentTileColor { get { return tileColor; } }

        #endregion Fields and Getters

        #region Construction and Reset

        /// <summary>
        /// Set up the game.
        /// </summary>
        public SlidingPuzzle() {
            InitializeComponent();
            resetGame();
        }

        /// <summary>
        /// Remove game board and reset all GUI elements.
        /// </summary>
        private void resetGame() {
            tileColor = DEFAULT_COLOR;
            numbersOn = true;
            tiles = DEFAULT_SIZE;
            tileSize = 0;
            movesLabelTitle.Hide();
            movesLabel.Text = "0";
            movesLabel.Hide();
            timeSoFar = 0;
            timeLabel.Text = "0:00:00";
            timeLabel.Hide();
            timeLabelTitle.Hide();
            gameTimer.Stop();
            updateSolvedLabel("No tiles");
            moves = 0;

            // remove each tile and structure holding them:
            if ( buttons != null ) {
                foreach ( Button b in buttons )
                    if (b!= null) // "blank tile"
                        b.Dispose();
                buttons = null;
            }

        } // method resetGame

        /// <summary>
        /// Keep same board and reset game to solved state.
        /// </summary>
        private void resetCurrentGame() {

            // if no current game, do nothing:
            if ( buttons == null )
                return;

            // stop and reset gameTime (might not be visible):
            gameTimer.Stop();
            timeLabel.Text = "0:00:00";
            timeSoFar = 0;
            updateSolvedLabel("Unscrambled");

            // reset moves:
            moves = 0;
            movesLabel.Text = "0";

            // move blank space to bottom, right corner
            // if button's there, swap locations in matrix:
            for (int row = 0; row < tiles; row++) {
                for (int col = 0; col < tiles; col++) {
                    if (row != tiles - 1 || col != tiles - 1) {

                        // exchange blank with last element in tile matrix:
                        if (buttons[col, row] == null) {
                            buttons[col, row] = buttons[tiles - 1, tiles - 1];
                            buttons[col, row].Location = new Point(col * tileSize, row * tileSize);
                            buttons[tiles - 1, tiles - 1] = null;
                        } // skip last element

                    } // don't do last tile
                } // cols
            } // rows

            // set position of blank tile:
            blankLoc = new Point(tileSize * (tiles - 1), tileSize * (tiles - 1));
            
            // move each button back to its original position:
            int count = 1;
            for (int row = 0 ; row < tiles ; row++) {
                for (int col = 0 ; col < tiles ; col++) {
                    // move tile with corresponding position ("count") 
                    // into this current spot in matrix and board:
                    if (row != tiles - 1 || col != tiles - 1) {
                        Button tmp = buttons[col, row];              // what's currently here:  
                        Button target = findButton(count);           // what should be here:
                        if (target != tmp) swapButtons(target, tmp); // do we need to move the current button?
                        count++;                                     // move to next button
                    } // skip last element
                } // end col
            } // end row

        } // method resetCurrentGame
        
        /// <summary>
        /// Find a particular tile based on button name (which is set by addTiles).
        /// </summary>
        /// <param name="buttons">all current tile buttons</param>
        /// <param name="name">name of tile</param>
        /// <returns>tile with input name; null if not found</returns>
        private Button findButton(int count) {
            foreach ( Button b in buttons ) {
                if ( b == null || b.Name == BUTTON_NAME + count ) {
                    return b;
                }
            }
            return null;
        } // method findButton
       
        #endregion Construction and Reset

        #region Start and Quit

        /// <summary>
        /// Start a new default game using built-in options.
        /// </summary>
        private void startDefaultGame() {




            // reset game parameters and defaults:
            resetGame();
            updateSolvedLabel("Unscrambled");

            // set up board:
            buttons = new Button[DEFAULT_SIZE, DEFAULT_SIZE];
            addTiles(DEFAULT_SIZE);

        } // method startDefaultGame 

        /// <summary>
        /// Start a new customized game.
        /// </summary>
        private void startCustomGame() {

            // Remove previous game:
            resetGame();

            // Open a customizing dialog modal form (http://msdn.microsoft.com/en-us/library/39wcs2dh.aspx)
            // Send main window object to access current color
            // (could simply by just sending current color):
            CustomGame newGame = new CustomGame(this);
            newGame.ShowDialog(new Form());

            // When user done customizing, access selected options:
            if ( newGame.DialogResult == DialogResult.OK ) {

                // tile display options:
                tiles = newGame.TileCount;       // new game size
                tileColor = newGame.TileColor;  // new tile color (if chosen)
                numbersOn = newGame.NumbersOn;  // are numbers on or off?

                // create new tiles:
                buttons = new Button[tiles, tiles];
                addTiles(tiles);

                // if image selected, load it and display on tile:
                if ( newGame.ImageFileName != null )
                    processImage(newGame.ImageFileName);

                // display moves?
                if ( newGame.MovesOn ) {
                    movesLabel.Show();
                    movesLabelTitle.Show();
                }

                // display timer?
                if ( newGame.TimerOn ) {
                    timeLabel.Show();
                    timeLabelTitle.Show();
                    timeSoFar = 0;
                }

                // restore unsolved alert:
                updateSolvedLabel("Unscrambled");

            } // end if

        } // method startCustomGame

        /// <summary>
        /// Quit current game.
        /// </summary>
        private void quit(FormClosingEventArgs e) {

            gameTimer.Stop();
            DialogResult result = 
                MessageBox.Show("Do you really want to quit?", "Quit?",
                                MessageBoxButtons.YesNo, MessageBoxIcon.Exclamation);
            if ( result == DialogResult.Yes )
                Dispose();
            e.Cancel = true; // keep form open if No!
            gameTimer.Start();

        } // method quit

        #endregion Start and Quit

        #region Buttons

        /// <summary>
        /// Reset the game.
        /// </summary>
        /// <param name="sender">Reset Board button</param>
        /// <param name="e"></param>
        private void resetButton_Click(object sender, EventArgs e) {
            resetCurrentGame();
        }

        /// <summary>
        /// Solve game. Currently not implemented (saving for a future GSD3 assignment).
        /// </summary>
        /// <param name="sender">Solve button</param>
        /// <param name="e"></param>
        private void solveButton_Click(object sender, EventArgs e) {
            solveCurrentGame();
        }

        /// <summary>
        /// Exit game.
        /// </summary>
        /// <param name="sender">Exit button</param>
        /// <param name="e"></param>
        private void exitButton_Click(object sender, EventArgs e) {
            quit(new FormClosingEventArgs(CloseReason.FormOwnerClosing, true));
        }

        /// <summary>
        /// Kill game window (from "X" button)
        /// </summary>
        /// <param name="sender">"X" button</param>
        /// <param name="e"></param>
        private void SlidingPuzzle_FormClosing(object sender, FormClosingEventArgs e) {
            quit(e);
        }

        /// <summary>
        /// Scramble current game board. Does nothing if no board.
        /// </summary>
        /// <param name="sender">Scramble Board button</param>
        /// <param name="e"></param>
        private void scrambleButton_Click(object sender, EventArgs e) {
            scrambleCurrentGame();
        }

        /// <summary>
        /// Start a "default game" (built-in parameters).
        /// </summary>
        /// <param name="sender">Default Game button</param>
        /// <param name="e"></param>
        private void defaultButton_Click(object sender, EventArgs e) {
            startDefaultGame();
        }

        #endregion Buttons

        #region Menus

        /// <summary>
        /// Show instructions.
        /// </summary>
        /// <param name="sender">Help->Instructions menu item</param>
        /// <param name="e"></param>
        private void instructionsToolStripMenuItem_Click(object sender, EventArgs e) {
            MessageBox.Show(
                "Press 'Default Game' or select menu 'Game->New Default Game' to load a built-in game. " +
                "To run a game with custom options, select menu 'Game->New Custom Game'. " +
                "\n\nPress 'Scramble' to enter how many times you want the computer to scramble the board. " +
                "The timer shows and starts if you have selected it in the custom options and scrambled the board." +
                "\n\nClick on a tile adjacent to a blank to move that tile into the blank. " +
                "\n\nThe game will report 'Solved!' when you get tiles in order from top-to-bottom, left-to-right, " +
                "with the blank in the bottom, right corner.",
                "Instructions" // dialog title
                );
        }

        /// <summary>
        /// Show "About" dialog.
        /// </summary>
        /// <param name="sender">Help->About menu item</param>
        /// <param name="e"></param>
        private void aboutToolStripMenuItem_Click(object sender, EventArgs e) {
            MessageBox.Show("Written by David I. Schwartz, 2009.");
        }

        /// <summary>
        /// Exit game.
        /// </summary>
        /// <param name="sender">Game->Exit menu item</param>
        /// <param name="e"></param>
        private void exitToolStripMenuItem_Click(object sender, EventArgs e) {
            quit(new FormClosingEventArgs(CloseReason.FormOwnerClosing, true));
        }

        /// <summary>
        /// Start a new customized game.
        /// </summary>
        /// <param name="sender">Game->New Custom Game menu item</param>
        /// <param name="e"></param>
        private void newCustomGameToolStripMenuItem_Click(object sender, EventArgs e) {
            startCustomGame();
        }

        /// <summary>
        /// Start default game.
        /// </summary>
        /// <param name="sender">Game->New Custom Game menu item</param>
        /// <param name="e"></param>
        private void newDefaultGameToolStripMenuItem_Click(object sender, EventArgs e) {
            startDefaultGame();
        }

        #endregion Menus

        #region Tile Creation

        /// <summary>
        /// Create and place tiles on board. Uses current tile color and size.
        /// </summary>
        /// <param name="numberOfTiles">Number of tiles on one side (num x num)</param>
        public void addTiles(int numberOfTiles) {

            // find smallest dimension of board to keep tiles square:
            int panelSize = Math.Min(gameContainer.Panel2.Width +
                gameContainer.Panel2.Margin.Left + gameContainer.Panel2.Margin.Right,
                gameContainer.Panel2.Height);

            // find size of each tile:
            tileSize = panelSize / numberOfTiles;

            // try to deal with roundoff error from tileSize
            // center on a panel that's inside Panel2:
            gameContainer.Panel2.Controls.Add(boardPanel);
            int diff = ( panelSize - ( tileSize * numberOfTiles ) ); // accumulated roundoff error
            boardPanel.Location = new Point(diff / 2, diff / 2);     // center panel (top,left corner)
            boardPanel.Width = panelSize;
            boardPanel.Height = panelSize;

            // populate board and "remember" order of tiles:
            int count = 1;
            for ( int row = 0; row < numberOfTiles; row++ ) {
                for ( int col = 0; col < numberOfTiles; col++ ) {

                    // don't put button in last position (bottom, right corner):
                    if (col != numberOfTiles - 1 || row != numberOfTiles - 1) {
                        buttons[col, row] = makeTile(count, col, row);
                        count++;
                    }

                }
            }

            // set location of "blank tile":
            blankLoc = new Point(tileSize * ( tiles - 1 ), tileSize * ( tiles - 1 ));
            buttons[tiles - 1, tiles - 1] = null; // redundant, but being a bit safer

        } // method addTiles

        /// <summary>
        /// Create a tile (as a button) and place in gameContainer (right panel).
        /// </summary>
        /// <param name="count">current tile number</param>
        /// <param name="col">board column location (grid)</param>
        /// <param name="row">board row location (grid)</param>
        /// <returns>newly made button at (col,row) location</returns>
        public Button makeTile(int count, int col, int row) {

            // Button provides "backing" of a tile:
            Button b = new Button();
            b.BackColor = tileColor;
            b.Margin = new System.Windows.Forms.Padding(0);
            b.Font = new System.Drawing.Font("Microsoft Sans Serif", 12F, System.Drawing.FontStyle.Bold,
                                             System.Drawing.GraphicsUnit.Point, ( (byte)( 0 ) ));
            b.Location = new System.Drawing.Point(col * tileSize, row * tileSize);
            b.Name = BUTTON_NAME + count;
            b.Size = new System.Drawing.Size(tileSize, tileSize);
            b.FlatStyle = FlatStyle.Flat;
            b.FlatAppearance.BorderSize = 1;
            b.FlatAppearance.BorderColor = Color.Black;
            b.Click += new EventHandler(tile_Click);
            if ( numbersOn ) b.Text = "" + count;
            boardPanel.Controls.Add(b);
            return b;

        } // method makeTile

        /// <summary>
        /// Load image and split onto tiles.
        /// </summary>
        /// <param name="fileName">full pathname of file</param>
        private void processImage(string fileName) {

            // attempt to split image into tiled bitmaps:
            try {

                // load image file to split later:
                Image tmp = new Bitmap(fileName);

                // need to calculate dimensions of board to account for borders:
                Panel s = gameContainer.Panel2;
                int width = s.Width + s.Margin.Left + s.Margin.Right;
                int height = s.Height + s.Margin.Top + s.Margin.Bottom;
                int dim = Math.Max(width, height);

                // convert image into bitmap resized into actual game board dimensions:
                Bitmap image = new Bitmap(tmp, dim, dim);

                // split image by copying the current (col*size,row*size) part as each tile's background:
                foreach ( Button b in buttons) {
                    if (b != null) {
                        int row = b.Location.Y;
                        int col = b.Location.X;
                        b.BackgroundImage = image.Clone(new Rectangle(col, row, tileSize, tileSize),
                                                        System.Drawing.Imaging.PixelFormat.DontCare);
                    }
                }

                // remove original image to save some space (as opposed to blizzard of buttons already created ;-)
                image = null;

            } // done trying to load/split image file:

            catch ( Exception ) {
                MessageBox.Show("Something wrong with processing Image file.");
            }

        } // method processImage

        #endregion Tile Creation

        #region Tile Motion

        /// <summary>
        /// Respond to tile clicking. If tile adjacent to blank space, swap locations.
        /// </summary>
        /// <param name="sender">particular tile clicked</param>
        /// <param name="e"></param>
        private void tile_Click(object sender, EventArgs e) {

            // clicked tile:
            Button currentButton = (Button)sender;

            // if any location is indeed empty, swap locations,
            // check if board is solved:
            if (adjacent(currentButton.Location, blankLoc)) {

                // yes, so swap locations and update move count:
                moveButton(currentButton);
                movesLabel.Text = (++moves) + "";

                // we might have a solved board:
                if (isSolved()) {
                    gameTimer.Stop(); // also updates solvedLabel
                    return;           // nothing else to search or check: 
                }

            } // end checking move to blank

            // board still unsolved:
            updateSolvedLabel("Unsolved");

        } // method tile_Click


        /// <summary>
        /// Return whether or not two Points are next to each other on the board.
        /// </summary>
        /// <param name="p1">first Point</param>
        /// <param name="p2">second Point</param>
        /// <returns>true if adjacent; otherwise false</returns>
        private bool adjacent(Point p1, Point p2) {
            return 
                (
                ( p1.X == p2.X - tileSize && p1.Y == p2.Y ) || // west
                ( p1.X == p2.X + tileSize && p1.Y == p2.Y ) || // east
                ( p1.Y == p2.Y - tileSize && p1.X == p2.X ) || // south
                ( p1.Y == p2.Y + tileSize && p1.X == p2.X )    // north
                );      
        }

        /// <summary>
        /// Check if a Point is a legal board position.
        /// </summary>
        /// <param name="p">Point to check</param>
        /// <returns>true if on board; otherwise false</returns>
        private bool inBounds(Point p) {
            return p.X >= 0 && p.X < tiles * tileSize &&
                   p.Y >= 0 && p.Y < tiles * tileSize;
        }

        /// <summary>
        /// Return a List of legal Points that are adjacent to the supplied Point.
        /// </summary>
        /// <param name="p"></param>
        /// <returns></returns>
        private List<Point> adjacencies(Point p) {
            List<Point> adj = new List<Point>(0);
            Point tmp;
            
            tmp = new Point(p.X - tileSize, p.Y); // west
            if ( adjacent(tmp,blankLoc) && inBounds(tmp) ) 
                adj.Add(tmp);

            tmp = new Point(p.X + tileSize, p.Y); // east
            if ( adjacent(tmp, blankLoc) && inBounds(tmp) )
                adj.Add(tmp);

            tmp = new Point(p.X, p.Y - tileSize); // north
            if ( adjacent(tmp, blankLoc) && inBounds(tmp) )
                adj.Add(tmp);

            tmp = new Point(p.X, p.Y + tileSize); // south
            if ( adjacent(tmp, blankLoc) && inBounds(tmp) ) 
                adj.Add(tmp);

            return adj;
        }

        /// <summary>
        /// Swap position of a tile with the blank.
        /// </summary>
        /// <param name="movedButton">Button to move to blank</param>
        private void moveButton(Button movedButton) {

            Point tmpLoc = movedButton.Location;
            Button tmpBtn = movedButton;

            movedButton.Location = blankLoc;
            buttons[blankLoc.X / tileSize, blankLoc.Y / tileSize] = movedButton;

            blankLoc = tmpLoc;
            buttons[tmpLoc.X / tileSize, tmpLoc.Y / tileSize] = null;
        }

        /// <summary>
        /// Swap positions of two tiles.
        /// </summary>
        /// <param name="b1">first tile</param>
        /// <param name="b2">second tile</param>
        private void swapButtons(Button b1, Button b2) {
            if (b1 == null)
                moveButton(b2);

            else if (b2 == null)
                moveButton(b1);

            else {

                // temp holder gets button to move:
                Point tmpLoc = b1.Location;
                Button tmpButton = b1;

                // move button to blank:
                b1.Location = b2.Location;
                buttons[b2.Location.X / tileSize, b2.Location.Y / tileSize] = b1;

                // move blank to where button was:
                b2.Location = tmpLoc;
                buttons[tmpLoc.X / tileSize, tmpLoc.Y / tileSize] = b2;

            }

        } // method swapButtons

        /// <summary>
        /// Scramble current board a user-supplied number of times.
        /// </summary>
        private void scrambleCurrentGame() {

            // nothing to scramble:
            if ( buttons == null )
                return;

            // reset counters:
            moves = 0;
            movesLabel.Text = "0";
            gameTimer.Stop();
            timeLabel.Text = "0:00:00"; // don't need to stop timer -- maybe custom game wants it to keep running?
            timeSoFar = 0;

            // disable buttons, menus, and tiles while scrambling (which can be lengthy)
            // want to avoid creating competing threads that attemtp to move/solve/move other games:
            allowControls(false);

            // prompt user to enter # of times to scramble board:
            TextInputDialog textInput = new TextInputDialog();
            textInput.ShowDialog(new Form());

            // get user input--proceed with scrambling if values OK:
            int scrambles = textInput.Scrambles;
            if ( scrambles > 0 && scrambles <= MAXSCRAMBLES ) {

                // OK -- time to scramble!
                // starting with blank, pick a random adjacent tile to swap
                // make the swap and repeat process:
                Random r = new Random();
                for ( int s = 0; s < scrambles; s++ ) {

                    // find adjacent locations to blank:
                    List<Point> dirs = adjacencies(blankLoc);

                    // pick one legal 0-4 (N,S,E,or W) neighbors of blank -- pick one
                    int choices = dirs.Count;                           // how many tiles could move to blank?
                    int randomChoice = r.Next(0, choices);              // pick random direction
                    Point p = dirs[randomChoice];                       // now have random location
                    Button b = buttons[p.X / tileSize, p.Y / tileSize]; // button at rand loc

                    moveButton(b); // swap that tile w/blank
                }

                // did we inadvertently solve the game?
                if ( !isSolved() )
                    updateSolvedLabel("Unsolved");
                else
                    updateSolvedLabel("Unscrambled!");

            } // end scrambles

            // re-enable the interface:
            allowControls(true);

            // restart the timer:
            gameTimer.Start();

        } // method scrambleCurrentGame

        #endregion Tile Motion

        #region Solving

        /// <summary>
        /// Solve current game.
        /// </summary>
        private void solveCurrentGame()
        {
            //Int array equivilant of goal gamestate. For any given size.
            int[] goal = new int[tiles * tiles];

            for (int x = 0; x < goal.Length; x++)
            {
                goal[x] = (x + 1);
                if (x == goal.Length - 1)
                {
                    goal[x] = 0;
                }
            }

            //Solution starts null.
            Node solution = null;

            //dialogue boxes let user pick a method. nested if/elseif statements go either through the yes/no chain to
            //the method the user wants, or else never calls any method and lets solution remain null.
            DialogResult bfscheck = MessageBox.Show("Should I use BFS?","Protip: Use A*", MessageBoxButtons.YesNoCancel, MessageBoxIcon.Question);

            if (bfscheck == DialogResult.Yes)
            {
                Queue<Node> open = new Queue<Node>();
                List<Node> closed = new List<Node>();
                Node startNode = new Node(convertButtonArrayToInts(), null,0,0);
                open.Enqueue(startNode);
                closed.Add(startNode);

                solution = bfs(open, closed, goal);

            }
            else if (bfscheck == DialogResult.No)
            {
                DialogResult dfscheck = MessageBox.Show("Should I use DFS?", "Protip: Use A*", MessageBoxButtons.YesNoCancel, MessageBoxIcon.Question);

                if (dfscheck == DialogResult.Yes)
                {
                    Stack<Node> open = new Stack<Node>();
                    List<Node> closed = new List<Node>();
                    Node startNode = new Node(convertButtonArrayToInts(), null, 0, 0);
                    open.Push(startNode);
                    closed.Add(startNode);

                    solution = dfs(open, closed, goal);
                }
                else if (dfscheck == DialogResult.No)
                {  
                    //Would have chained into an IDFS solve query, but IDFS was unfortunately giving me trouble. -Rob
                    /*    DialogResult idfscheck = MessageBox.Show("How about IDFS?", "Protip: Use A*", MessageBoxButtons.YesNoCancel, MessageBoxIcon.Question);
                        if (idfscheck == DialogResult.Yes)
                        {
                            Stack<Node> open = new Stack<Node>();
                            List<Node> closed = new List<Node>();
                            Node startNode = new Node(convertButtonArrayToInts(), null,0,0);
                            open.Push(startNode);
                            closed.Add(startNode);

                            solution = idfs(open, closed, goal);
                        }
                        else if (idfscheck == DialogResult.No)
                        {*/
                    DialogResult astarcheck = MessageBox.Show("So A*?", "You totally want A*", MessageBoxButtons.OKCancel, MessageBoxIcon.Exclamation);

                    if (astarcheck == DialogResult.Yes)
                    {
                    }
                }
            }
            

            if (solution != null)
            {
                //DoStuffHereWithSolution
            }



            // Placeholder approach below! 
            // In future GSD3 assignment, we can actually solve with something called recursion and graphs.
            // if game timer on, stop and reset?
            //resetCurrentGame();
        }


        /// <summary>
        /// Starting from initial gamestate (put into queue and closed list), find every child, add them to the queue and closed list,
        /// then check all of their children, and on and on, until we find the end.
        /// </summary>
        /// <param name="open">Queue with starting node already Queued.</param>
        /// <param name="closed">List with starting node already added.</param>
        /// <param name="goal">Goal array, should be [1, 2, 3,....n-1, n, 0].</param>
        /// <returns></returns>
        private Node bfs(Queue<Node> open, List<Node> closed, int[] goal)
        {
            

            while (open.Count > 0) 
            {
                Node currentState = open.Dequeue();

                if (!altIsSolved(currentState.Data, goal))
                {
                    List<int[]> childs = Children(currentState.Data);
                    for (int i = 0; i < childs.Count; i++)
                    {
                        Node tmp = new Node(childs[i], currentState,0,0);

                        if (!closed.Contains(tmp))
                        {
                            open.Enqueue(tmp);
                            closed.Add(tmp);
                        }
                    }
                }
                else
                {
                    return currentState;
                }
            }

            return null;
        }

        /// <summary>
        /// Starting from initial gamestate (put into queue and closed list), find the children and throw them on the stack, then find
        /// further children to throw on the stack. inefficient.
        /// </summary>
        /// <param name="open">Stack with starting node already pushed.</param>
        /// <param name="closed">List with starting node already added.</param>
        /// <param name="goal">Goal array, should be [1, 2, 3,....n-1, n, 0].</param>
        /// <returns></returns>
        private Node dfs(Stack<Node> open, List<Node> closed, int[] goal)
        {


            while (open.Count > 0)
            {
                Node currentState = open.Pop();

                if (!altIsSolved(currentState.Data, goal))
                {
                    List<int[]> childs = Children(currentState.Data);
                    for (int i = 0; i < childs.Count; i++)
                    {
                        Node tmp = new Node(childs[i], currentState,0,0);

                        if (!closed.Contains(tmp))
                        {
                            open.Push(tmp);
                            closed.Add(tmp);
                        }
                    }
                }
                else
                {
                    return currentState;
                }
            }

            return null;
        } 

        /// <summary>
        /// Starting from initial gamestate (put into queue and closed list), find the children and throw them on the stack, then find
        /// further children to throw on the stack. However if child is too far down from initial, don't put it on stack. when all children
        /// are pulled off the stack, increase the depth limit and do it all again.
        /// 
        /// Does not seem to work. Sadface.
        /// </summary>
        /// <param name="open">Stack with starting node already pushed.</param>
        /// <param name="closed">List with starting node already added.</param>
        /// <param name="goal">Goal array, should be [1, 2, 3,....n-1, n, 0].</param>
        /// <returns></returns>
       /* private Node idfs(Stack<Node> open, List<Node> closed, int[] goal)
        {
            int depth = 0;
            int depthLimit = 1;
            Node initial = open.Pop();

            for(;depthLimit < 100000; depthLimit++)
            {
                open.Clear();
                open.Push(initial);
                depth = 0;
            while (open.Count > 0)
            {
                Node currentState = open.Pop();

                if (!altIsSolved(currentState.Data, goal))
                {
                    List<int[]> childs = Children(currentState.Data);

                    for (int i = 0; i < childs.Count; i++)
                    {
                        Node tmp = new Node(childs[i], currentState,0,currentState.Depth + 1);

                        if (!closed.Contains(tmp) && tmp.Depth < depthLimit)
                        {
                            open.Push(tmp);
                            closed.Add(tmp);
                        }
                        else
                        {
                            for (int x = 0; x < closed.Count; x++)
                            {
                                if (closed[x].Equals(tmp))
                                {
                                    if (tmp.Depth < closed[x].Depth)
                                    {
                                        closed[x].Depth = tmp.Depth;
                                        open.Push(tmp);
                                    }
                                    break;
                                }
                            }
                           
                        }
                    }
                }
                else
                {
                    return currentState;
                }
            }
            
            }

            return null;
        }*/

        private int[] convertButtonArrayToInts()
        {
            int[] toReturn = new int[(tiles * tiles)];
            int index = 0;
            for (int row = 0; row < tiles; ++row)
            {
                for (int col = 0; col < tiles; ++col)
                {
                    Button tmp = buttons[col, row];

                    if (tmp != null)
                    {
                        string buttonNumberString = tmp.Name.Substring(BUTTON_NAME.Length);
                        toReturn[index] = int.Parse(buttonNumberString);
                        index++;
                    }
                    else
                    {
                        toReturn[index] = 0;
                        index++;
                    }
                }
            }

            return toReturn;


        }

        private Button[,] convertIntArrayToButtons(int[] array)
        {
            Button[,] toReturn = new Button[tiles, tiles];

            int index = 0;
            for (int row = 0; row < tiles; row++)
            {
                for (int col = 0; col < tiles; col++)
                {

                    // don't put button in last position (bottom, right corner):
                    if (array[index] != 0)
                    {
                        toReturn[col, row] = makeTile(array[index], col, row);
                        index++;
                    }
                    else
                    {
                        toReturn[col, row] = null;
                        index++;
                    }

                }
            }

            return toReturn;

        }

        private List<int[]> Children(int[] array)
        {
            List<int[]> children = new List<int[]>();
            int indexofZero = 0;
            for (int x = 0; x < array.Length; x++)
            {
                if (array[x] == 0)
                { indexofZero = x; }
            }

            int zeroColumn = indexofZero % tiles;
            int zeroRow = indexofZero / tiles;

 

            int checkColumn;
            int checkRow;

            for (int x = 0; x < array.Length; x++)
            {
                checkColumn = x % tiles;
                checkRow = x / tiles;

                if (Math.Abs((checkColumn - zeroColumn)) == 1 && checkRow - zeroRow == 0 || (Math.Abs((checkRow - zeroRow)) == 1 && checkColumn - zeroColumn == 0))
                {
                    int[] Copy = new int[array.Length];
                    for (int y = 0; y < array.Length; y++)
                    {
                        Copy[y] = array[y];
                    }
                    Copy[indexofZero] = array[x];
                    Copy[x] = 0;
                    children.Add(Copy);
                }
            }

            return children;

        }

        private int ManhattanDistance(int[] toCheck, int[] goal)
        {
            int totalDistance = 0;

            for (int index = 0; index < toCheck.Length; index++)
            {
                int numbertoFind = index;
                int indexofNumbertoFind = -1;

                for (int x = 0; x < toCheck.Length; x++)
                {
                    if (toCheck[x] == numbertoFind)
                    {
                        indexofNumbertoFind = x;
                    }
                }
                
                int distancex = 0;
                int distancey = 0;

                int columnofNumber = indexofNumbertoFind % tiles;
                int rowofNumber = indexofNumbertoFind / tiles;

                if (numbertoFind != 0)
                {
                    distancex = columnofNumber - ((numbertoFind - 1) % tiles);

                    if (distancex < 0)
                    {
                        distancex = distancex * -1;
                    }

                    distancey = rowofNumber - ((numbertoFind - 1) / tiles);

                    if (distancey < 0)
                    {
                        distancey = distancey * -1;
                    }
                }
                else
                {
                    distancex = columnofNumber - ((toCheck.Length - 1) % tiles);

                    if (distancex < 0)
                    {
                        distancex = distancex * -1;
                    }

                    distancey = rowofNumber - ((toCheck.Length - 1) / tiles);

                    if (distancey < 0)
                    {
                        distancey = distancey * -1;
                    }
                }

                totalDistance += (distancex + distancey);

            }

            return totalDistance;
        }



        private bool altIsSolved(int[] state, int[] goal)
        {
           for(int x = 0; x < goal.Length; x++)
           {
               if (state[x] != goal[x])
               { return false; }
           }

           return true;

        } // method isSolved





        /// <summary>
        /// Check if current board in solved state.
        /// </summary>
        /// <returns>true if solved; else false</returns>
        private bool isSolved() {
            //
            // Courtesy of Zach Hoefler, 2010
            //
            // bottom-right button must be empty, otherwise
            // solution is not done
            if (buttons[tiles - 1, tiles - 1] == null) {
                int previousButtonNumber = 0;
                for (int row = 0; row < tiles; ++row) {
                    for (int col = 0; col < tiles; ++col) {
                        Button tmp = buttons[col, row];

                        if (tmp != null) {
                            string buttonNumberString = tmp.Name.Substring(BUTTON_NAME.Length);
                            int buttonNumber = int.Parse(buttonNumberString);
                            // int buttonNumber = int.Parse(tmp.Text);

                            if (buttonNumber != previousButtonNumber + 1)
                                return false;

                            previousButtonNumber = buttonNumber;
                        }
                    }
                }
                updateSolvedLabel("Solved!");
                MessageBox.Show("The puzzle is solved!");
                return true;
            }
            else {
                return false;
            }
         
        } // method isSolved

        #endregion Solving

        #region Interface Updates

        /// <summary>
        /// Set and adjust solved label (changes due to different messages).
        /// </summary>
        /// <param name="msg">message to put in label</param>
        private void updateSolvedLabel(string msg) {

            solvedLabel.Text = msg;

            // there are better variable names out there:
            SplitContainer wc = statusContainer;       // "width container"
            SplitterPanel hc = statusContainer.Panel1; // "height container"
            Label lbl = solvedLabel;                   // our label to place

            // label's x coord = (width of container - width of label)/2:
            int width1 = wc.Width + wc.Margin.Left + wc.Margin.Right;
            int width2 = lbl.Width + lbl.Margin.Left + lbl.Margin.Right;
            int x = ( width1 - width2 ) / 2;

            // labels's y coord = (height of container - height of label)/2:
            int height1 = hc.Height + hc.Margin.Top + hc.Margin.Bottom;
            int height2 = lbl.Height + lbl.Margin.Top + lbl.Margin.Bottom;
            int y = ( height1 - height2 ) / 2;

            // center label width and height:
            solvedLabel.Location = new System.Drawing.Point(x, y);

        } // method updateSolvedLabel

        /// <summary>
        /// Disable buttons/menus on interface while scrambling/solving
        /// to prevent starting competeting threads.
        /// </summary>
        /// <param name="allowal">true to enable controls, else false</param>
        private void allowControls(bool allowal) {
            solveButton.Enabled = allowal;
            scrambleButton.Enabled = allowal;
            menuStrip1.Enabled = allowal;
            resetButton.Enabled = allowal;
            foreach ( Button b in buttons )
                if (b!=null) // blank tile
                    b.Enabled = allowal;
            defaultButton.Enabled = allowal;
        } // method allowControls

        /// <summary>
        /// Update game timer in human-readable form (hours:min:sec).
        /// </summary>
        /// <param name="sender">Game Timer</param>
        /// <param name="e"></param>
        private void gameTimer_Tick(object sender, EventArgs e) {

            // each tick adds 1 sec to current time:
            timeSoFar++;

            // calculate h, m, s:
            int hours = timeSoFar / 3600;
            string min = ( timeSoFar % 3600 ) / 60 + "";
            string sec = ( timeSoFar % 60 ) + "";

            // handle single-digit min and sec:
            if ( int.Parse(sec) < 10 ) sec = "0" + sec;
            if ( int.Parse(min) < 10 ) min = "0" + min;

            // update label:
            timeLabel.Text = hours + ":" + min + ":" + sec;

        }

        #endregion Interface Updates

    } // class SlidingPuzzle

} // namespace SlidingPuzzle